class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n == 0:
            return [""]

        result = []
        for i in range(n):
            left = self.generateParenthesis(i)
            right = self.generateParenthesis(n-i-1)
            result = result + [ "(" + l + ")" + r for l in left for r in right]
        return result